//给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
//
// 例如： 
//给定二叉树 [3,9,20,null,null,15,7], 
//
//     3
//   / \
//  9  20
//    /  \
//   15   7
// 
//
// 返回其自底向上的层次遍历为： 
//
// [
//  [15,7],
//  [9,20],
//  [3]
//]
// 
//

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    fun levelOrderBottom(root: TreeNode?): List<List<Int>> {
        //中序遍历 + 逆序
        val result = mutableListOf<List<Int>>()
        levelOrder(root, 0, result)
        result.reverse()
        return result
    }

    fun levelOrder(root: TreeNode?, level:Int, result: MutableList<List<Int>>){
        root?:return
        val currentLevel :MutableList<Int> = if(result.size > level){
            result[level] as MutableList<Int>
        }else{
            mutableListOf<Int>().also {
                result.add(it)
            }
        }
        currentLevel.add(root.`val`)
        levelOrder(root.left, level+1, result)
        levelOrder(root.right, level+1, result)


    }
}